/*
 * One example for NOI CSP-J Lesson 8:
 * <https://courses.fmsoft.cn/plzs/noijunior-other-data-structures.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

// 返回可被放入容量为 W 的背包中的最大价值。
int knapsack_r(int W, vector<int> &val, vector<int> &wt, int n) {

    // Base Case
    if (n == 0 || W == 0)
        return 0;

    int pick = 0;

    // 如果第 n 个物品不超过背包的容量，则选择该物品。
    if (wt[n - 1] <= W)
        pick = val[n - 1] + knapsack_r(W - wt[n - 1], val, wt, n - 1);
                            //  注意， ^ 这里传入的是减去第 n 个物品后的容量

    // 计算不选择该物品时，得到的价值。
    int notPick = knapsack_r(W, val, wt, n - 1);

    // 返回价值较高的情形。
    return max(pick, notPick);
}

int knapsack(int W, vector<int> &val, vector<int> &wt) {
    int n = val.size();
    return knapsack_r(W, val, wt, n);
}

int main() {
    vector<int> val = {1, 2, 3};
    vector<int> wt = {4, 5, 1};
    int W = 10;

    cout << knapsack(W, val, wt) << endl;
    return 0;
}

